﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;

namespace dst
{
    class AddExp<T> : Exp where T : Exp
    {
        List<T> subExps = new List<T>();
        bool ordered = false;

        public T this[int i]
        {
            get { return subExps[i]; }
        }

        public int Count
        {
            get { return subExps.Count; }
        }

        private AddExp()
        {
            this.sig = 0;
        }

        private void AddSubExp(params T[] exps)
        {
            AddSubExp(-1, exps);
        }

        private void AddSubExp(int iExc, params T[] exps)
        {
            for (int i = 0; i < exps.Length; i++)
            {
                if (i != iExc)
                {
                    if (subExps.Contains(exps[i]))
                    {
                        subExps.Remove(exps[i]);
                        this.sig -= exps[i].Sign;
                    }
                    else
                    {
                        subExps.Add(exps[i]);
                        this.sig += exps[i].Sign;
                    }
                }
            }
            this.sig %= Util.P128;
            if (this.sig < 0)
                this.sig += Util.P128;
        }

        public static Exp GetAdd(params T[] eles)
        {
            AddExp<T> m = new AddExp<T>();
            m.AddSubExp(eles);
            //if (m.subExps.Count == 0)
            //    return Exp.Zero;
            //else if (m.subExps.Count == 1)
            //    return (Ele)Util.simpTable.Add(m.Sign, m);
            //else
            return (Exp)Util.simpTable.Add(m.Sign, m);
        }

        public static Exp GetAdd(int i, params T[] eles)
        {
            AddExp<T> m = new AddExp<T>();
            m.AddSubExp(i, eles);
            //if (m.subExps.Count == 0)
            //    return Exp.Zero;
            //else
            return (Exp)Util.simpTable.Add(m.Sign, m);
        }

        public static Exp GetAdd(T a, params T[] eles)
        {
            AddExp<T> m = new AddExp<T>();
            m.AddSubExp(a);
            m.AddSubExp(eles);
            
            return (Exp)Util.simpTable.Add(m.Sign, m);
        }

        public static Exp GetAdd(T[] t1s, T[] T2s)
        {
            AddExp<T> m = new AddExp<T>();
            m.AddSubExp(t1s);
            m.AddSubExp(T2s);
            
            return (Exp)Util.simpTable.Add(m.Sign, m);
        }

        public static Exp GetAdd(T[] t, bool inc, params int[] idxs)
        {
            if (inc)
            {
                T[] exps = new T[idxs.Length];
                for (int i = 0; i < idxs.Length; i++)
                    exps[i] = t[idxs[i]];

                return GetAdd(exps);
            }
            else
            {
                throw new NotImplementedException();
            }
        }

        protected override Exp Add(Exp a)
        {
            if (a is Ele)
            {
                if (a == Exp.Zero)
                    return this;
                else
                    return AddExp<Exp>.GetAdd(a, this.subExps.ToArray());
            }
            else if (a is MulExp<Exp>)
                return AddExp<Exp>.GetAdd(a, this.subExps.ToArray());
            else if(a.GetType().Name.Contains("AddExp"))
                return AddExp<Exp>.GetAdd(this.subExps.ToArray(), ((AddExp<Exp>)a).subExps.ToArray());
            else
                throw new NotImplementedException();
        }

        protected override Exp Mul(Exp a)
        {
            if (a == Exp.Zero)
                return Exp.Zero;
            else if (a == Exp.Unit)
                return this;
            else
                throw new NotImplementedException();
        }

        public override bool Contains(Exp e)
        {
            for (Dictionary<string, BigInteger>.Enumerator enu = e.SubSigns.GetEnumerator(); enu.MoveNext(); )
            {
                if (!this.SubSigns.ContainsKey(enu.Current.Key))
                    return false;

                if(enu.Current.Value != (enu.Current.Value & this.SubSigns[enu.Current.Key]))
                    return false;
            }
            return true;
        }

        public override int CompareTo(Exp other)
        {
            if (other is AddExp<Exp>)
            {
                int min = this.subExps.Count < ((AddExp<Exp>)other).subExps.Count ? this.subExps.Count : ((AddExp<Exp>)other).subExps.Count;
                for (int i = 0; i < min; i++)
                {
                    int r = this.subExps[i].CompareTo(((AddExp<Exp>)other).subExps[i]);
                    if (r != 0)
                        return r;
                }

                if (this.subExps.Count > min)
                    return 1;
                else if (((AddExp<Exp>)other).subExps.Count > min)
                    return -1;
                else
                    return 0;
            }
            else
                return 0;
        }

        public override void SortSubs()
        {
            if (ordered == false)
            {
                this.subExps.Sort();
                this.ordered = true;
            }
        }

        public override void MakeSubSign()
        {
            for (int i = 0; i < this.subExps.Count; i++)
            {
                if (this.subExps[i] is Ele)
                {
                    Dictionary<string, BigInteger>.Enumerator enu = this.subExps[i].SubSigns.GetEnumerator();
                    enu.MoveNext();

                    if(this.subSigns.ContainsKey(enu.Current.Key))
                    {
                        this.subSigns[enu.Current.Key] ^= enu.Current.Value;
                    }
                    else
                    {
                        this.subSigns.Add(enu.Current.Key, enu.Current.Value);
                    }
                }
                else
                    throw new NotImplementedException();
            }
        }

        public override Exp Factor(params Ele[] es)
        {
            AddExp<T> backup = this.Clone();
            backup.subExps.Sort();
            AddExp<Exp> r = new AddExp<Exp>();

            int j = 0;
            T sub = backup.subExps[j];
            for (int i = 0; i < es.Length; i++)
            {
                AddExp<Exp> subAdd = new AddExp<Exp>();
                while (sub.Contains(es[i]))
                {
                    subAdd.AddSubExp(sub.Factor(es[i]));
                    j++;
                    if (j == backup.subExps.Count)
                        break;
                    sub = backup.subExps[j];
                }
                r.subExps.Add(Util.simpTable.Add(subAdd.Sign, subAdd));
            }

            return r;
        }

        /// <summary>
        /// 生成闭包
        /// </summary>
        /// <returns></returns>
        public override HashSet<Exp> GenClosure()
        {
            HashSet<Exp> r = new HashSet<Exp>();
            r.Add(this);

            Queue<Exp> todo = new Queue<Exp>();
            if (this.subExps.Count > 2)
                todo.Enqueue(this);

            while (todo.Count > 0)
            {
                AddExp<T> e = (AddExp<T>)todo.Dequeue();
                for (int i = 0; i < e.subExps.Count; i++)
                {
                    Exp adde = AddExp<Exp>.GetAdd(i, e.subExps.ToArray());
                    r.Add(adde);
                    if (e.subExps.Count > 3)
                        todo.Enqueue(adde);
                }
            }

            return r;
        }

        /// <summary>
        /// 生成元素个数为vol的闭包
        /// </summary>
        /// <param name="vol"></param>
        /// <returns></returns>
        public override List<Exp> GenClosure(int vol)
        {
            if (vol != 2)
                throw new NotImplementedException();

            List<Exp> r = new List<Exp>();

            for (int i = 0; i < this.Count; i++)
            {
                for (int j = i + 1; j < this.Count; j++)
                {
                    r.Add(AddExp<Exp>.GetAdd(this.subExps.ToArray(), true, i, j));
                }
            }

            return r;
        }

        

        public AddExp<T> Clone()
        {
            AddExp<T> r = new AddExp<T>();
            r.sig = this.sig;
            r.subExps.AddRange(this.subExps);

            return r;
        }

        public override Exp Replace(Exp old, Exp now)
        {
            if (now is Ele)
            {
                if (this.Contains(old))
                    return this + old + now;
                else
                    throw new Exception("Nothing to replace!");
            }
            else
                throw new NotImplementedException();
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < subExps.Count; i++)
                sb.Append(subExps[i].ToString() + "+");

            string s = sb.ToString();
            if (s.Length > 0)
                s = s.Substring(0, s.Length - 1);

            return s;
        }
    }
}
